package com.hcl.sort;

import java.util.Arrays;

/**
 * 快速排序
 * 1、选择最左边元素作为基准点
 * 2、j指针负责从右向左找比基准点小的元素，i之战负责从左向右找比基准点大的元素，一旦找到二者交换，直到i、j相交
 * 3、最后基准点与i(此时i与j相等)交换，i就是分区的位置
 */
public class QuickSortDemo {
    public static void main(String[] args) {
        int[] array = {4,6,5,2,9,3};
        quickSort(array,0,array.length-1);
        System.out.println("array = " + Arrays.toString(array));
    }

    public static void quickSort(int[] array,int left,int right){
        if (left > right){
            return;
        }
        // 选择最左边元素作为基准点
        int piv = array[left];
        int l = left;
        int r = right;
        while (l < r){
            // 先从右往左找，找比基准点小的
            while (l < r && array[r] >= piv){
                r--;
            }
            // 从左往右找，找比基准点大小
            while (l < r && array[l] <= piv){
                l++;
            }
            // 此时找到交换元素
            int temp = array[r];
            array[r] = array[l];
            array[l] = temp;
        }
        // 最后基准点与i(此时i与j相等)交换 array[left]基准端
        int temp = array[left];
        array[left] = array[l];
        array[l] = temp;

        // 左边递归
        quickSort(array,left,l-1);
        // 右边递归
        quickSort(array,l+1,right);
    }
}
